package com.zdp.util;

/*
* 并查集： 关于并查集 ， 用于处理一些不相交集合的合并问题
*  相关概念： 1. 集合的代表 ----> 每一个并查集有且仅有一个代表，在同一个并查集中的元素的代表都应该相同
* 2. 并查集中的代表指向自己，其余的元素指向自己的上级
* 相关操作： 1. 创建并查集
* 2. 合并并查集
* 3. 查找并查集的代表
* */
public class UnionFindSets {
    public int[] parent;
    public void init(int n){
        // 创建一个并查集
        parent = new int[n];
        // 初始化并查集
        for(int i=0;i<n;i++){
            parent[i] = i;
        }
    }

    /*
    * 合并并查集： 将一个集合的代表指向另一个集合的代表
    * 一般是 将包含节点较少的代表 指向包含节点较多的代表
    * */
    public void unionSet(int index1,int index2){
        parent[findParent(index1)] = findParent(index2);
    }

    /*
    * 查找并查集的代表 , 查找的同时进行路径压缩 ----> 所有的元素直接指向代表
    * */
    public int findParent(int index){
        if(parent[index] != index){
            parent[index] =  findParent(parent[index]);
        }
        return parent[index] ;
    }
    /*
    * 非递归版本
    * */
    public int findParent1(int index){
        int result = index;
        // 找到代表节点
        while(parent[result] != result){
            result = parent[result];
        }
        // 路径压缩
        int t;
        while(index != result){
            t = parent[index];
            parent[index] = result;
            index = t;
        }
        return result;
    }
}
